package com.ywgt;

import java.util.*;

/**
 * 贪心算法，每次都会选择最优解，但是结果不一定是最优
 */
public class Greedy {

    public static void main(String[] args) {
        //有五个电台，每个电台的广播范围不同，求取使用最少的电台，能够覆盖全部的城市
        HashMap<String, HashSet<String>> map = new HashMap<>();
        List<String> cities=new LinkedList<>();
        HashSet<String> hashSet1=new HashSet<>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");
        map.put("K1",hashSet1);
        HashSet<String> hashSet2=new HashSet<>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        map.put("K2",hashSet2);
        HashSet<String> hashSet3=new HashSet<>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        map.put("K3",hashSet3);
        HashSet<String> hashSet4=new HashSet<>();
        hashSet4.add("上海");
        hashSet4.add("天津");
        map.put("K4",hashSet4);
        HashSet<String> hashSet5=new HashSet<>();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        map.put("K5",hashSet5);
        cities.add("北京");
        cities.add("大连");
        cities.add("杭州");
        cities.add("天津");
        cities.add("上海");
        cities.add("成都");
//        cities.add("深圳");
//        cities.add("广州");
        List<String> info = getInfo(map, cities);
        System.out.println(info);
    }

    /**
     * 求取最少的电台集合
     * @param map 每个电台对应的城市范围
     * @param cities 要匹配的城市
     * @return
     */
    public static List<String> getInfo(HashMap<String, HashSet<String>> map,List<String> cities){
        //创建map的索引key，为了后面删除map中对应的key-value，和添加返回结果
        String index=null;
        //创建一个集合指针循环遍历时使用
        List<String> temp=new LinkedList<>();
        //返回结果集
        ArrayList<String> info=new ArrayList<>();
        while(cities.size()>0){//当城市的集合不为空时一直遍历，知道找到覆盖完的城市
            int nums=0;//定义一个指针，用来记录当前循环中的最大的匹配数量
            for(String entry:map.keySet()){ //循环map
                temp.addAll(cities); //每次循环重新向指针中添加剩余未匹配的城市元素
                HashSet<String> hashSet = map.get(entry);
                temp.retainAll(hashSet); //当前key-value中与指针中相等的城市的交集，赋值给指针
                int size = temp.size();//获取指针中的元素大小
                if(size>nums){
                    index=entry; //将每次遍历的结果最大值保存 以及将最大匹配值map的key记录下来，后面要从map中移除
                    nums=size;
                }
                temp.clear();//每次比较完，清空指针，方便下次遍历前重新赋值比较
            }
            HashSet<String> hashSet = map.get(index);//获取最多匹配值的key-value
            cities.removeAll(hashSet);//从原始集合中移除
            map.remove(index);//从map中将已经匹配过的元素删除
            info.add(index);//将key加入到返回的结果集
        }
        return info;
    }

}
